package com.cat.graphTheory;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-moves-to-clean-the-classroom/description/
 * @create 2025/9/23 17:18
 * @since JDK17
 */

public class Solution25 {
    public int minMoves(String[] classroom, int energy) {
        int n = classroom.length, m = classroom[0].length(), tot = 0, ans = 0;
        int[] s = null, d = new int[] { -1, 0, 1, 0, -1 };
        char[][] g = new char[n][m];
        int[][] h = new int[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = classroom[i].toCharArray();
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'S') {
                    s = new int[] { i, j, energy, 0 };
                }
                if (g[i][j] == 'L') { // 垃圾收集
                    h[i][j] = 1 << tot++;
                }
            }
        }
        int u = 1 << tot;
        boolean[][][][] vis = new boolean[n][m][energy + 1][u];
        Deque<int[]> q = new ArrayDeque<>();
        q.add(s);
        vis[s[0]][s[1]][s[2]][0] = true;
        while (!q.isEmpty()) {
            for (int i = 0, end = q.size(); i < end; i++) {
                var p = q.pollFirst();
                if (u - 1 == p[3]) { // 收集了所有的垃圾
                    return ans;
                }
                if (p[2] == 0) {
                    continue;
                }
                for (int j = 0; j < 4; j++) {
                    int nx = p[0] + d[j], ny = p[1] + d[j + 1], e = p[2], k = p[3];
                    if (nx == -1 || nx == n || ny == -1 || ny == m || g[nx][ny] == 'X') {
                        continue;
                    }
                    e = g[nx][ny] == 'R' ? energy : e - 1;
                    k = k | h[nx][ny];
                    if (!vis[nx][ny][e][k]) {
                        vis[nx][ny][e][k] = true;
                        q.addLast(new int[] { nx, ny, e, k});
                    }
                }
            }
            ans++;
        }

        return -1;
    }
}
